from typing import List


class Solution:
    """
    方法：快速选择算法
    
    Args:
        nums: List[int], 输入数组
        k: int, 第k大的元素
        
    Returns:
        int: 数组中第k大的元素
        
    Time: O(n), 平均情况下，每次划分将问题规模减半
    Space: O(logn), 递归调用栈的深度
    """
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        return self.quickSelect(nums, 0, n - 1, n - k)
    def quickSelect(self, nums: List[int], l: int, r: int, k: int) -> int:
        if l == r:
            return nums[k]
        x = nums[l]
        i = l -1
        j = r + 1
        while i<j:
            while True:
                i += 1
                if nums[i] >= x:
                    break;
            while True:
                j -= 1
                if nums[j] <= x:
                    break;
            if i < j:
                nums[i], nums[j] = nums[j], nums[i]
        if k <= j:
            return self.quickSelect(nums, l, j, k)
        else:
            return self.quickSelect(nums, j + 1, r, k);

    """
    方法：使用最小堆查找第k大元素
    维护一个大小为k的最小堆，堆顶元素即为当前第k大元素。遍历数组，当遇到比堆顶大的元素时，替换堆顶并调整堆结构。
    
    Args:
        nums: List[int], 输入数组
        k: int, 第k大的元素
        
    Returns:
        int: 数组中第k大的元素
        
    Time: O(nlogk), 构建堆需要O(k)时间，处理剩余元素需要O((n-k)logk)时间
    Space: O(1), 原地修改数组，不使用额外空间
    """

    def findKthLargest1(self, nums: List[int], k: int) -> int:
        def build_min_heap(arr, size):
            for i in range(size // 2 - 1, -1, -1):
                heapify(arr, i, size)
        def heapify(arr, i, size):
            left = 2 * i + 1
            right = 2 * i + 2
            smallest = i
            if left < size and  arr[left] < arr[smallest]:
                smallest = left
            if right < size and arr[right] < arr[smallest]:
                smallest = right
            if smallest != i:
                arr[i], arr[smallest] = arr[smallest], arr[i]
                heapify(arr, smallest, size)
        
        # 构建初始最小堆
        build_min_heap(nums, k)
        # 处理剩余元素
        for i in range(k, len(nums)):
            if nums[i] > nums[0]:
                nums[0] = nums[i]
                heapify(nums, 0, k)
        return nums[0]

    """
    方法：使用最小堆查找第k大元素
    维护一个大小为k的最小堆，堆顶元素即为当前第k大元素。遍历数组，当遇到比堆顶大的元素时，替换堆顶并调整堆结构。
    
    Args:
        nums: List[int], 输入数组
        k: int, 第k大的元素
        
    Returns:
        int: 数组中第k大的元素
        
    Time: O(nlogk), 构建堆需要O(k)时间，处理剩余元素需要O((n-k)logk)时间    
    Space: O(1), 原地修改数组，不使用额外空间
    """

    def findKthLargest2(self, nums, k):
        def heapify2(arr, n, i):
            # Adjust the subtree rooted at i to be a min-heap
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
            # Find the minimum value among the current node, left child node,and right child node 
            if left < n and arr[left] < arr[smallest]:
                smallest = left
            if right < n and arr[right] < arr[smallest]:
                smallest = right
            # if the minmum value is not the current node,swap and continue adjusting
            if smallest != i:
                arr[i], arr[smallest] = arr[smallest], arr[i]
                heapify2(arr, n, smallest)


        heap = nums[:k]
        # bulid minimum heap
        for i in range(k // 2 - 1, -1, -1):
            heapify2(heap, k, i)
        # Travers the remaining elements while maintaining the heap size not excedds k
        for num in nums[k:]:
            # the current element is larger than the top of the heap
            if num > heap[0]:
                # replace the top of the heap
                heap[0] = num
                # adjust the heap
                heapify2(heap, k, 0)
        # The top of the heap is the Kth largest element
        return heap[0]
     
        